题目: 678. 有效的括号字符串

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

• 任何左括号 ( 必须有相应的右括号 )。
• 任何右括号 ) 必须有相应的左括号 ( 。
• 左括号 ( 必须在对应的右括号之前 )。
• * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
• 一个空字符串也被视为有效字符串。

题解: 贪心

先假设如果没有*的时候，我们只需要遍历一次字符串，初始 flag 为 0

• 如果遍历到(，则flag ++
• 如果遍历到)，则flag --

遍历完之后，flag也为0则说明匹配。注意：在遍历的过程中，flag不能为负数。

如今增添了 *，当字符为*，会出现三种情况：

1. flag++
2. flag--
3. flag不变

为了应付这三种情况，我们使用两个变量来记录字符的变化,maxFlag，minFlag

• 如果遍历到(，则maxFlag++，minFlag ++
• 如果遍历到)，则maxFlag--，minFlag-- 当遇到 * 时：

1. maxFlag++
2. minFlag--

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
    let maxFlag =0,minFlag = 0
    for(let i of s){
        if(i === '('){
            maxFlag++
            minFlag++
        }
        if(i === ')'){
            maxFlag--
            minFlag = minFlag-1>0?minFlag-1:0
            if(maxFlag<0) return false
        }
        if(i === '*'){
            minFlag = minFlag-1>0?minFlag-1:0
            maxFlag++
        }
    }
    return minFlag === 0
};

参考资料

1. 678. 有效的括号字符串 (opens new window)
2. 官方题解 (opens new window)